package 堆;

import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * https://leetcode-cn.com/problems/top-k-frequent-elements/
 *
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 */
public class _347_前K个高频元素 {

    private HashMap<Integer,Integer> hashMap = new HashMap<>();
    private PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer k1, Integer k2) {
            //通过哈希表中的值去比较
            return hashMap.get(k1) - hashMap.get(k2);
        }
    });

    public int[] topKFrequent(int[] nums, int k) {
        if(nums == null || nums.length == 0) return new int[0];

        //将数组的元素作为key,出现次数作为value,加入到哈希表中
        for(int i=0;i< nums.length;++i){
            //已存在的情况，就将value+1
            if(hashMap.containsKey(nums[i])){
                hashMap.put(nums[i],hashMap.get(nums[i])+1);
            }else{
                hashMap.put(nums[i],1);
            }
        }

        for(Integer key: hashMap.keySet()){
            if(heap.size()<k){
                heap.add(key); //建立最小堆
            }else if(hashMap.get(key) > hashMap.get(heap.peek())){
                //对于第k+1个数，通过key拿到出现次数value进行比较
                heap.remove();
                heap.add(key);
            }
        }

        int[] newNums = new int[heap.size()];
        for(int i=0;i< newNums.length;++i){
            newNums[i] = heap.poll();
        }

        return newNums;
    }


}
